#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int KeyType;

typedef struct node
{
	KeyType key;
	struct node *lchild, *rchild;
}BSTNode;

BSTNode * create (KeyType *, int);
bool insert_bst (BSTNode **, KeyType);
void print (BSTNode *);
void destroy (BSTNode *);
bool delete_bst (BSTNode **, KeyType);
void mydelete (BSTNode **);
void delete_db_node (BSTNode *, BSTNode **);

int main ()
{
	KeyType arr[6] = {19, 98, 10, 20, 40, 15};
	BSTNode *mybst = create(arr, 6);
	print(mybst);
	printf("\n");
	delete_bst(&mybst, 40);
	print(mybst);
	printf("\n");
	destroy(mybst);
	
	return 0;
}

void print (BSTNode *bst)
{
	if (bst != NULL) {
		print(bst->lchild);
		printf("%d ", bst->key);
		print(bst->rchild);
	}
}

void destroy (BSTNode *bst)
{
	if (bst != NULL) {
		destroy(bst->lchild);
		destroy(bst->rchild);
		free(bst);
	}
}

BSTNode * create (KeyType *arr, int n)
{
	BSTNode *mybst = NULL;
	int i = 0;
	
	while (i < n) {
		insert_bst(&mybst, arr[i]);
		++i;
	}

	return mybst;
}

bool insert_bst (BSTNode **bst, KeyType k)
{
	if (*bst == NULL) {

		*bst = (BSTNode *)malloc(sizeof(BSTNode));
		(*bst)->key = k;
		(*bst)->lchild = (*bst)->rchild  = NULL;
		return true;
	
	} else {
		
		if (k == (*bst)->key) {
			return false;
		} else if(k < (*bst)->key) {
			
			return insert_bst(&(*bst)->lchild, k);

		} else {

			return insert_bst(&(*bst)->rchild, k);
		
		}
	
	}
}

bool delete_bst (BSTNode **bst, KeyType k)
{
	if ((*bst) == NULL)
		return false;

	if (k == (*bst)->key) {
		mydelete(bst);
		return true;
	} else if (k < (*bst)->key) {
		return delete_bst(&(*bst)->lchild, k);
	} else {
		return delete_bst(&(*bst)->rchild, k);
	}
}

void mydelete (BSTNode **ppToDelete)
{
	BSTNode *pTmp = NULL;
	
	if ((*ppToDelete)->rchild == NULL) {

		pTmp = *ppToDelete;
		*ppToDelete = (*ppToDelete)->lchild;
		free(pTmp);

	} else if ((*ppToDelete)->lchild == NULL) {
		
		pTmp = *ppToDelete;
		*ppToDelete = (*ppToDelete)->rchild;
		free(pTmp);
		
	} else {
		delete_db_node(*ppToDelete, &(*ppToDelete)->lchild);
	}
}

void delete_db_node (BSTNode *pToReplace, BSTNode **ppToDelete)
{
	BSTNode *pTmp = NULL;
	
	if ((*ppToDelete)->rchild != NULL) {

		delete_db_node(pToReplace, &(*ppToDelete)->rchild);

	} else {
		pToReplace->key = (*ppToDelete)->key;
		pTmp = *ppToDelete;
		*ppToDelete = (*ppToDelete)->lchild;
		free(pTmp);
	}
}
